
\documentstyle{article}
\topmargin 0in \textheight 434pt
\evensidemargin 0.5in \oddsidemargin 0.5in
\textwidth 360pt \marginparwidth 0in \marginparsep 0pt

\begin{document}
\title{LCAU.DOC}

\author{
Harold V. McIntosh \\
Departamento de Aplicaci\'on de Microcomputadoras,\\
Instituto de Ciencias, Universidad Aut\'onoma de Puebla,\\
Apartado postal 461, 72000 Puebla, Puebla, M\'exico.}

\date{\today}
\maketitle 

\begin{abstract} 
A previous collection of celular automata programs has been extended in 
three directions; also certain minor errors have been corrected. 
\begin{enumerate} 
\item General rules, not just totalistic rules, may be analyzed.
\item Cell densities and block probabilities may be calculated 
according to mean field theory and local structure theory using options 
in a new submenu.
\item An option to produce de~Bruijn diagrams is incorporated in another 
new submenu. 
\end{enumerate} 
Consequently a more detailed and convenient analysis of $(k,1), k=2,3,4$ 
and $(2,2)$ automata may be made than previously.  
\end{abstract}

The disk LCAU.C supplements the disk LCA.C which was released in the 
summer of 1987. Both source code and a separate disk of .EXE files are 
provided. The original disk contained 9 programs written in ``C'' to 
calculate and display the evolution of linear cellular automata. 
Although the programs represented a point in the evolution of the 
course {\em Fortran III} offered during the past several semesters, at 
the {\em Universidad Aut\'onoma de Puebla}, and were promoted at the 
{\em XVI Feria de Puebla}, they had their principal inspiration in an 
article in the December, 1986, issue of Byte magazine which explained 
how cellular automata could lead to intricate and complicated designs, 
with a certain aesthetic appeal. 

\begin{quotation} 
\noindent
	Kenneth E. Perry, \\
	Abstract mathematical art, \\
	Byte, December 1986, pages 181-192. 
\end{quotation} 

The 9 programs in the LCAkr.C set ran through the $k$-range of 2, 3, 
and 4 states per cell, as well as interactions between first, second, 
or third neighbors (the $r$-range). The combinations (4,1) and (4,2) 
are surely the most colorful, but the binary first neighbor version 
(2,1) is more amenable to an exhaustive analysis.

Programs in the new series are named LCAU to distinguish them from 
members of the old series. 

In the old series, In all cases except for (2,1), only totalistic rules 
were considered. Totalistic rules are those for which the transition 
depends only on the number of cells of different kinds in each 
neighborhood, but not on their precise arrangement. More exactly, each 
state gets assigned an integer in the range 0 to $k-1$ as a weight, the 
actual transition being a function of the weighted sum of all the 
neighbors (including the evolving cell). The artistic effects arise 
from assigning colors to each of cell values. 

Although the use of totalistic rules serves to reduce the enormous 
number of possible automata greatly, it excludes many interesting 
possiblilities arising from a more detailed specification of the 
evolutionary rules. When k, the number of states per cell is small, 
there is not too much which is possible in the way of design, but once 
it reaches 4 or beyond some interesting constructions become possible. 
LCA41.C in particular, contains enhanced rule and line editing menus 
which allow experimentation with the design of rules.

Certain of the demonstrations in LCAU41.C show how the design process 
can be used. There is an example of a ``binary counter'' which consists 
of a glider gun together with bistable targets. In one state the target 
absorbs the glider and changes to the other state. In the second state 
the target passes the glider, reverting to the first state. Thus half 
the gliders are lost to each target, whose state forms a binary counter 
whose carry is represented by the gliders which are allowed to pass. 

Another demonstration shows how a bouncing glider may shuttle between 
two obstacles - still lifes - drawing them ever closer together. Just 
as the glider is about to be crushed, the walls coalesce but the glider 
escapes to one side, seeking new walls to conquer. Multiple gliders may 
go about their business, competing for the wall if they lie on opposite 
sides or hastening the squeeze if they lie on the same side.

A third demonstration shows a slow glider propelled by an internal 
glider or gliders bouncing back and forth - a sort of Mexican jumping 
bean. When a fast glider overtakes a slower glider, they coalesce, 
producing an even slower glider. 

A fourth demonstration shows gliders of two different velocities, which
can be used to set up a remote still life whose reaction to further 
gliders gives it a life of its own. 

Such constructions can be used to generate interesting patterns, but 
they also serve theoretical ends as well. For example, the binary 
counters establish the existence of structures with both exponentially 
long transients and exponentially long cycles. Since they still use 
several cells to establish the basic components and their spacings, 
they still do not reach theoretical maxima; but they do lie within 
certain factors of such maxima.

When $k$ becomes larger still, universal Turing machines can be 
programmed, but this probably requires a $k$ of at least 6 or 8.

Another extensive addition which has been made to the programs is to be 
found in the series PROB.C, which can be invoked by typing $t$ in the 
main menu (the old totalistic rule number can still be utilized by 
typing $T$); in fact their inclusion more than doubles the size of the 
programs. These new programs permit a statistical survey of the 
properties of the automaton. Originally they calculated simple 
probabilities on the basis of ideas which go by the name of ``mean field 
theory,'' whose results were plausible but not entirely convincing.

Since then two interesting articles have appeared 

\begin{quote} 
\noindent
	W. John Wilbur, David J. Lipman and Shihab A. Shamma, \\
	On the 	prediction of local patterns in cellular automata, \\
	Physica {\bf 19D} 397-410 (1986).

\noindent
	Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight, \\
	Local structure theory for cellular automata, \\
	Physica {\bf 28D} 18-48 (1987). 
\end{quote} 

These articles, from differing points of view, show how to take 
correlations between cells into account by calculating the 
probabilities of strings of cells. Rather than taking individual 
probabilties as fundamental and deducing the probabilities of 
combinations, the process is inverted; self consistent probabilities 
for strings (or blocks) of a certain length are found from which the 
probabilities of individual cells are obtained by averaging.

The calculations of these articles have been included among the options 
of the $t$ submenu, so that probabilities derived from blocks of length 
up to 6 can be compared with simpler estimates and with the actual 
performance of the automaton.

A third feature of the new series is the incorporation of the de Bruijn 
diagrams within the main program, together with a visual representation 
in terms of chords of a circle. It is still not possible to transfer 
the cycles obtained back to the main program without copying them on 
paper and editing the initial line with the option $l$. Limitations of 
space and time severely restrict the lengths of periods which can be 
analyzed. Although interesting gliders and cycles are found within the 
accessible range of the program, there are many others of longer 
periods which manifest themselves experimentally when the evolutions 
are run. It would be nice if the exhaustive analysis afforded by the 
de Bruijn diagrams were feasible for the longer periods that show up on 
the screen, but they would really require a faster computer, more 
memory, and probably programs incorporating finer details of the 
algorithms used. 

The programs contain a bare minimum of help facilities, in the sense 
that menus of one type or another are presented at various stages in 
the evolution of the programs, and others are sometimes available by 
typing a question mark, just as a slash will often clear portions of 
the screen. 

A manual consisting of the lecture notes for {\em Fortran III} is in 
preparation, for which chapters are planned describing the accompanying 
programs. As is well known, the preparation of manuals always lags the 
evolution of the programs which they are supposed to describe.

There are still some interesting problems of presentation - recall that 
{\em Fortran III} is supposed to be dedicated to graphical techniques{\bf !} 
Presentation of simple evolution is easily solved, since the resolution 
and velocity of the graphics controllers included as standard equimpent 
in IBM PC's and clones is adequate. Unfortunately color monitors and 
their controllers are sometimes seen as premium equipment which was not 
included in a given installation, so that a monochromatic rendering of 
the color displays must be endured.

Even so, the speed and screen resolution which is available in the 
present generation of equipment is only marginally satisfactory, having 
only a fraction of the resolution of pen and ink plotters which have 
been commonly available. Once statistics pertaining to the evolution of 
automata are to be presented, it is found that there are many more 
parameters than are comfortable, which leads to the use of shading, 
complex surface representations, even stereographic views. It is in 
this area that some interesting results can be obtained, but mostly 
ones which whet one's appetite for the next generation of equipment.

Likewise the use of the de Bruijn diagram and the reduced evolution 
diagram, even without their probabilistic versions, requires line 
drawings of a complexity which quickly surpasses the capability of the 
present generation of graphical displays. Although the complexity of 
these diagrams increases exponentially - making even modest values of 
parameters permanently inaccessible; still, even moderately better 
graphics equipment will permit an instructive display of the simplest 
cases.

Although the menus vary slightly from program to program, they 
generally conform to a uniform pattern, whose constituents are 
described below.

\begin{list}{}{}

\begin{figure}[ht]
\centering
\fbox{\rule{0mm}{60mm}\rule{100mm}{0mm}} 
\caption{copyright notice} 
\end{figure} 

\item[The Copyright Notice (Figure~1)] - The initial screen in all 
programs bears a copyright notice and a very short description of the 
program. While the inexperienced user is reading the screen, a random 
number generator is wasting time, so that there will usually be a 
different display every time the program is run; likewise a different 
sequence of random rules and initial lines. No effort has been made to 
see how much this initial idling degenerates the performance of the 
random number generator.

\begin{figure}[ht]
\centering 
\fbox{\rule{0mm}{45mm}\rule{110mm}{0mm}} 
\caption{the main menu, showing rule and line} 
\end{figure} 

\item[The Main Menu (Figure~2)] - The main menu generally offers the 
following selection, whose details vary slightly from one automaton to 
another: 

\begin{list}{}{}
\item[r] - edit the rule 
\item[l] - edit the line 
\item[q] - quit 
\item[g] - graph the evolution 
\item[x] - generate a random rule 
\item[y] - generate a random line 
\item[u] - generate a sparse line
\item[T] - edit a totalistic rule number

\item[\#nn] - execute stored rule number nn 
\item[@nn] - execute totalistic rule number nn 
\item[\$nn] - execute 12 totalistic rules starting with number nn 
\item[wnn] - execute Wolfram rule number nn (LCAU21 only) 

\item[t] - enter probabilistic submenu 
\item[d] - enter de Bruijn submenu 
\end{list} 

Additional commands are present in different programs, but they are not 
publicized because they are generally experimental. In future versions 
of the programs they may be officially documented. Anyone persisting in 
a desire to use them at their own risk may discover them by studying 
the source code. 

The following list is fairly reliable, although the options do not 
appear on any of the screens presented to the user: 

\begin{list}{}{}
\item[.] - the line evolves for one generation 
\item[=] - repeat the first 40 cells 8 times 
\item[~] - repeat the first 20 cells 16 times 
\item[D] - display all stored rules in sequence 
\item[Y] - symmetrize the rule 
\item[Z] - (sometimes z) clear the line 
\end{list} 

The $.$ instruction is particularly useful when an interesting 
structure has been found on the general screen, but it is evolving too 
fast or it is hard to pick out fine details clearly at the resolution 
of the screen. By returning to the main menu (using any keystroke 
followed by y) the evolution can be followed one generation at a time, 
and either recorded by a screen dump or noted by hand on a scrap of 
paper.

Similarly it is possible to transfer the results of the de~Bruijn 
diagram or any other interesting string to the line menu, then return 
to the main menu to follow their evolution closely with the dot 
command. 

The instructions which repeat the initial segment of the line can be 
used to increase the variance in some of the probabilistic studies, and 
to force the automaton to enter a cycle sooner than otherwise. 
Nevertheless, for most rules a ring of 20 cells is still much too long to 
reach a cycle within a thousand generations. 

In contrast to the old programs, the new programs contain very few 
sample rules. By recompiling, one could add further examples that 
seemed worth preserving; in any event the command $D$ allows the 
samples to be reviewed and thus is useful for presenting demonstrations. 
No doubt some future edition of these programs will allow rule files to 
be read from disk, as well as allowing the storage of interesting rules 
which have been found during the course of execution of a program. 

\begin{figure}[ht]
\centering
\fbox{\rule{0mm}{20mm}\rule{120mm}{0mm}} 
\caption{the rule editor works on the bottom line of the array 
relating neighborhoods (top lines) to their image (last line).} 
\end{figure} 

\item[The Rule Editing Menu (Figure~3)] - To edit a rule, either 
general or totalistic, one may move the cursor and insert values for 
the cell above the cursor. Some programs have a more elaborate cursor, 
with tabs, wraparound, and the possibility of flagging values which 
will not be altered by using the random rule generator $x$ ($X$ overrides 
the flags). Again these features are experimental, and may possibly be 
confirmed in future versions of the programs. Later on the special 
commands which apply to LCAU41 are shown. 

\begin{figure}[ht]
\centering
\fbox{\rule{0mm}{35mm}\rule{120mm}{0mm}} 
\caption{the line editor works on the line of cells, which is divided 
into 8 lines of 40 cells.} 
\end{figure} 

\item[The Line Editing Menu (Figure~4)] - Lines are edited by 
essentially the same procedures that the rules are, but the long line 
of 320 cells is broken down into 8 lines 40 cells, to make movement 
across the line using the up and down arrows more rapid. LCAU41, which 
corresponds to one of the simplest automata for which rules may be 
designed to order, has many additional line editing options, all 
experimental, which can be used to facilitate the design. No doubt more 
will be added before the existence of all of them is officially 
announced. 

\begin{figure}[htp]
\centering
\fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} 
\caption{a typical screen within the probabalistic submenu, showing the 
placement of the different options. Typing ? will summon the menu.} 
\end{figure} 

\item[The Probabilistic Submenu (Figure~5)] - By typing $t$ one arrives 
at a separate display, implemented in the programs PROB.C, which will 
perform several statistical analyses of their automata. The programs 
vary considerably with the number of states, since they attempt to 
represent the relative probabilities as points within a simplex. For 
two states, the results are trivial, for three states the diagrams are 
planar and interesting, for four states the graphical capabilities of 
the screen are strained; for five and beyond some other representation 
would be required. 

The generic options are: 

\begin{list}{}{}
\item[a] - a priori estimates 
\item[m] - evolution of cells and pairs 
\item[M] - 50 generation evolution of cells and pairs 
\item[g] - 50 generation evolution of single cells
\item[G] - 200 generation evolution of single cells
\item[s] - graph probabilities in stereo 
\item[t] - graph probabilities, show contours in simplex 
\item[1] - 1-block local structure theory iterations 
\item[2] - 2-block local structure theory iterations 
\item[3] - 3-block local structure theory iterations 
\item[4] - 4-block local structure theory iterations 
\item[5] - 5-block local structure theory iterations 
\item[6] - 6-block local structure theory iterations 
\item[+] - select blue-cyan-white
\item[-] - select red-green-yellow
\item[e] - show 16 lines of evolution 
\item[/] - clear screen
\item[?] - show menu
\item[carriage return] - exit 
\end{list} 

Options 5 or 6 may not be available if they require too much time or 
space, $t$ shows two-block probabilities for k=2 automata, and there may 
be variants on $s$. For $k=2$, the commands $x$, $y$, $z$, $w$, $v$, $i$, 
and $j$ produce graphs for self-consistent 1-block probabilities for 
varying numbers of generations and numbers of iterations. 

\begin{figure}[htp]
\centering
\fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} 
\caption{a typical screen within the de~Bruijn submenu, showing the 
placement of the different options. Typing ? will cause the menu to 
appear.} 
\end{figure} 

\item[The de Bruijn Submenu(Figure~6)] - There are two kinds of de 
Bruijn diagrams that can be computed - those showing the counterimages 
of a uniform string, and those which isolate strings satisfying a 
certain combination of shifting and periodicity. Letters are assigned 
to them consecutively, but the combination of period and displacement 
varies widely because of the differing number of combinations possible. 

The de~Bruijn submenu is entered by typing $d$ in the main menu, to 
execute a program RIJN.C which is nearly self-contained. In general 
terms, the commands of the submenu are 

\begin{list}{}{} 
\item[1,2,...] - generates a de Bruijn diagram of n stages
\item[a,b,c,...] - shows cyclic counterimages
\item[A,B,C,...] - shows all counterimages 
\item[other letters] - show (p,d) cycles 
\item[+,-] - selects the color palette 
\item[?,/] - clears screen, shows menu
\item[carriage return] - exits
\end{list} 

To obtain information from the de Bruijn submenu will probably require 
the use of pencil and paper, or the use of the screen dump program. 
Although the program lists all the links in the de Bruijn diagram, the 
ring diagram is generally too cluttered to use directly from the screen 
and should be redrawn. Usually the resulting diagram can be further 
simplified, often it contains many redundant loops. Used casually, it 
still shows whether there will be many or few periods of a given type.
\end{list} 

\begin{figure}[htp]
\centering 
\fbox{\rule{0mm}{110mm}\rule{124mm}{0mm}} 
\caption{a typical screen showing the rule number and 192 lines 
of evolution} 
\end{figure} 

Figure~7 shows a typical screen of evolution. Evolutionary screens may 
be interrupted at any line by pressing any key; alternatives will then 
be offered to continue the display (carriage return), exit the program 
(n), or return to the main menu (nominally y, but it is the default). 
It is a general principle in all parts of the program, that the 
keystroke which interrupts any activity is discarded. Therefore a new 
activity cannot be initiated by simply typing its letter, although 
typing it twice in succession will usually work. 

Designing rules to order, which first becomes interesting for (4,1) 
automata, is a sufficiently interesting activity that it is worth 
documenting some of the otherwise hidden options in the main menu, rule 
editor, and line editor of LCAU41.C; nevertheless they are strictly 
experimental and may well be changed as experience in their use grows. 
In any event they require considerable skill. 

\begin{list}{}{}
\item[main menu] - special commands for rule design 

\begin{list}{}{}
\item[U] - push rule and flags 
\item[V] - pop rule and flags 
\item[G] - fetch rule and flags without popping 
\item[x] - random values for unflagged transitions 
\item[X] - random values for all transitions 
\item[1] - some particular transitions
\item[2] - other particular transitions
\end{list} 

\item[rule editor] - special commands for rule design 

\begin{list}{}{}
\item[0,1,2,3] - define transition 
\item[tab] - next quad = cursor fast advance
\item[space] - advance cursor 
\item[back] - return cursor 
\item[up] - set flag 
\item[down] - remove flag 
\end{list} 

\item[line editor] - special commands for rule design 

\begin{list}{}{}
\item[0,1,2,3] - define cell 
\item[arrows] - move about cell array
\item[$<,>$] - move to margin 
\item[z] - clear one row 
\item[Z] - clear entire line 
\item[x] - clear flags 
\item[q] - uniform color 
\item[=] - adapt rule to transition at cursor 
\item[*] - adapt rules to all transitions in one segment 
\item[.] - evolve cell under cursor 
\item[?] - evolve entire segment from the one above 
\item[/] - conditional evolution of segment (mark unflagged transitions) 
\item[c] - test consistency of one cell - inconsistent cell marked red 
\item[c] - test consistency of all cells - inconsistent cells marked red 
\end{list} 

\end{list} 

\begin{figure}[htp]
\centering 
\fbox{\rule{0mm}{85mm}\rule{124mm}{0mm}} 
\caption{evolution of a (4,1) rule whose behaviour is that of a binary 
counter} 
\end{figure} 

Figure~8, on the next page, shows the evolution of a (4,1) binary 
counter. Many rules can be found in which gliders, still lifes, and 
oscillators go about various simple activities; it is only necessary to 
do a certain amount of experimentation. It is an open question as to 
what the minimum combination of states and neighborhood is needed to 
obtain the behaviour of a Turing machine, but some examples are known 
of one sided automata interacting with a single neighbor which suffice. 
Nevertheless there are many interesting combinations which are still 
less complicated than a universal Turing machine, some of which just 
might be universal in their own way. 

end

\end{document}
